/*
 * =====================================================================================
 *
 *       Filename:  3-11.cpp
 *
 *    Description:  编程之美 3.11程序改错
 *
 *        Version:  1.0
 *        Created:  2011-11-15 14:46:56
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

#include <iostream>
#include <iterator>
#include "UserTime.h"

template <class Comparable>
int binary_search(Comparable array[], int n, const Comparable &v)
{
    int l = 0, r = n - 1;

    while (l <= r) {
        int m = l + (r - l) / 2;

        if (v > array[m]) {
            l = m + 1;
        } else if (v < array[m]) {
            r = m - 1;
        } else {
            return m;
        }
    }

    return -1;
}

template <class Comparable>
int lower_bound(Comparable array[], int n, const Comparable &v)
{
    int l = -1, r = n;

    while (r - l > 1) {
        int m = l + (r - l) / 2;

        if (v > array[m]) {
            l = m;
        } else {
            r = m;
        }
    }

    if (r >= n || array[r] != v) {
        r = -1;
    }

    return r;
}

template <class Comparable>
int upper_bound(Comparable array[], int n, const Comparable &v)
{
    int l = -1, r = n;

    while (r - l > 1) {
        int m = l + (r - l) / 2;

        if (v < array[m]) {
            r = m;
        } else {
            l = m;
        }
    }

    if (l <= -1 || array[l] != v) {
        l = -1;
    }

    return l;
}

template <class Comparable>
int find_maxi_lower(Comparable array[], int n, const Comparable &v)
{
    int pos = lower_bound(array, n, v);
    return (0 <= pos && pos <= n - 1) ? --pos : -1;
}

template <class Comparable>
int find_mini_upper(Comparable array[], int n, const Comparable &v)
{
    int pos = upper_bound(array, n, v);
    return (0 <= pos && pos <= n - 2) ? ++pos : -1;
}

int main(int argc, char *argv[])
{
    int A[] = {1, 2, 3, 3, 3, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 9};
    const int cnt = sizeof(A) / sizeof(int);
    std::copy(A, A + cnt, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    int unsorted[] = {3, 4, 1, 2, 3, 4, 2, 10, 31, 22, 1, 34, 32, 22, 21};
    std::copy(unsorted, unsorted + sizeof(unsorted) / sizeof(int), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    int tmp = 0;

    while (std::cin >> tmp) {
        std::cout << "binary search process on the sorted array :" << std::endl;
        std::cout << "binary_search the pos of " << tmp << " is " << binary_search(A, cnt, tmp) << std::endl;
        std::cout << "lower_bound the pos of " << " is " << lower_bound(A, cnt, tmp) << std::endl;
        std::cout << "upper_bound the pos of " << " is " << upper_bound(A, cnt, tmp) << std::endl;
        std::cout << "find_maxi_lower the pos of " << " is " << find_maxi_lower(A, cnt, tmp) << std::endl;
        std::cout << "find_mini_upper the pos of " << " is " << find_mini_upper(A, cnt, tmp) << std::endl;

        std::cout << "binary search process on the unsorted array :" << std::endl;
        std::cout << "binary_search the pos of " << tmp << " is " << binary_search(unsorted, cnt, tmp) << std::endl;
        std::cout << "lower_bound the pos of " << " is " << lower_bound(unsorted, cnt, tmp) << std::endl;
        std::cout << "upper_bound the pos of " << " is " << upper_bound(unsorted, cnt, tmp) << std::endl;
        std::cout << "find_maxi_lower the pos of " << " is " << find_maxi_lower(unsorted, cnt, tmp) << std::endl;
        std::cout << "find_mini_upper the pos of " << " is " << find_mini_upper(unsorted, cnt, tmp) << std::endl;

    }


    return 0;
}
